package com.huawei.controller;

import java.util.Stack;

/**
 * description
 *
 * @author cwx1134046
 * @since 2023-01-18
 */
public class SmallestSubsequence {

    /**
     *返回 s 字典序最小的子序列，该子序列包含 s 的所有不同字符，且只包含一次。
     *
     * 注意：该题与 316 https://leetcode.com/problems/remove-duplicate-letters/ 相同
     *
     * 示例 1：
     *
     * 输入：s = "bcabc"
     * 输出："abc"
     * 示例 2：
     *
     * 输入：s = "cbacdcbc"
     * 输出："acdb"
     *
     * 提示：
     *
     * 1 <= s.length <= 1000
     * s 由小写英文字母组成
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/smallest-subsequence-of-distinct-characters
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     *
     */

    public static String smallestSubsequence(String s) {

        Stack<Character> stack = new Stack<>();

        for (int i =0 ; i< s.length() ; i++ ) {
            Character c = s.charAt(i);

            if(stack.isEmpty()){
                stack.push(c);
                continue;
            }
            Character peek;
            // 栈顶元素比当前元素大，且后续存在，且栈中不存在，则出栈
            while ( !stack.isEmpty()
                    && (peek = stack.peek())>c
                    && s.substring(i).contains(peek.toString())
                    && !stack.contains(c)) {
                stack.pop();
            }
            if(!stack.contains(c)){
                stack.push(c);
            }
        }

        StringBuffer buffer = new StringBuffer();
        for (Character c:stack) {
            buffer.append(c);
        }
        return buffer.toString();
    }
    //abcacb
    public static void main(String[] args) {
        smallestSubsequence("cbaacabcaaccaacababa");
    }
}
